前言

为什么会有这个东西呢？主要是我在做这个题单的时候，发现省选的时候这些算法都过过一遍，但是掌握情况相当的差。其他的题单也有部分的知识是我没有掌握到的。

所以，为了更好的完成这些题单，也为了为之后在省选有完备的的资料可查，或者为之后的人铺平道路，整理以下的内容。

。

为了能够及时更新，你会在我拖更的地方看到这样一句友情提示：

这里有你没写完的东西，杂鱼...

大纲

动态规划

常见基础动态规划

 

 

 

 

背包

 

 

 

 

动规常见优化

倍增优化 数据结构优化

动态DP

图论

最短路

floyd

spfa

dijkstra

johnson

差分约束

最小生成树

prim

kruskal

最近公共祖先(LCA)

tarjan(连通分量问题)

scc(强连通分量)

割边-edcc(边双连通分量)

割点-vdcc(点双连通分量)

二分图

网络流

FF-EK-Dinic

费用流

上下界流

模拟费用流

2-SAT

二分图最大权匹配

最小树形图

仙人掌与圆方树

数据结构

树状数组

线段树

序列线段树

值域线段树

可持久化线段树

线段树合并

线段树分裂

ZKW线段树

并查集

普通并查集

扩展域并查集

权值并查集

莫队

普通莫队

带修莫队

回滚莫队

树上莫队

笛卡尔树

树套树

线段树二分/树状数组倍增

多树二分

整体二分

CDQ分治

线段树分治

重链剖分

长链剖分

平衡树

Splay

FHQ-Treap

(李超线段树)

(动态树)

(快速傅里叶变换)

(快速数论变换)

Prufer序列

可并堆

斜堆

随机堆

左偏树

KDT

数学

质数的判定

暴力

埃氏筛

欧拉筛

Miller–Rabin

卡特兰数

威尔逊定理

错排列

圆排列

多重集排列组合

BSGS与EXBSGS

生成函数

普通生成函数

指数生成函数

狄利克雷生成函数

狄利克雷卷积

莫比乌斯反演

亚线性筛法

杜教筛

PN筛

min_25筛

第一类斯特林数

第二类斯特林数

斯特林反演

二项式反演

Burnside定理

Polya定理

博弈论

二次剩余

线性基

字符串

字符串哈希

KMP

EXKMP

ACAM(AC自动机)

SAM(后缀自动机)

SA(后缀数组)

tricks

序列操作转差分

注：

：AM 在字符串中，默认指 ，即自动机。

动态规划

常见基础动态规划

背包

动规常见优化

动规的优化也是一门高深的学问。

动规核心要素包括状态、阶段和决策。动规的优化主要从第 方面入手进行优化。

对于状态，我们有时会通过题目中的性质，压缩掉其中的某些维度，比如 Mobile Service 一题中我们通过一定有一个员工在请求的位置，压缩掉了一维，省掉了一个 ；有时候我们会重新设计状态，使得他能够包括更多的本质相同的状态，比如固定点数的不同构 DAG 计数，等等。

更加常见的优化从对于决策，或者说转移的方面入手。一般来说我们会通过各种各样的手段，达到压缩转移次数（比如倍增优化，矩阵快速幂优化，CDQ优化等），快速找到决策点（比如单调队列优化，各种数据结构优化，斜率优化，贪心优化，四边形不等式优化等），快速统计转移贡献（比如前缀和优化，各种数据结构优化，离散化，贪心优化，费用提前计算等），以及各种各样针对问题特点特例化出来的各类模型（比如背包，树形DP，数位DP等）。

总而言之，我们的核心思想就是压缩状态，减少阶段，加速决策，从而达到更优的效率。

倍增优化

倍增优化的基础原理就是他把 段给暴力拆分成了 段，通过适当的预处理，将平均的时间复杂度中的 降到 。讲完了，看例题：

T1：有一些线段，问你至少要多少条线段才能覆盖掉 这个区间。

这个是最简单的一道题，可以预处理出每个左端点用 条线段最远能覆盖到哪个右端点， 解决。不给代码了。

T2。

我们不难发现暴力匹配的问题就在于太过暴力了（废话），所以我们考虑优化。

我们想到的第一个优化类似于建立索引，让你匹配的时候能够快速地跳到下一个该匹配的位置，但是实际上并没有优化复杂度。

第二个优化就比较关键了：我们考虑将字符串视为一个整体进行匹配，也就是说我们计算出跳完一整个 或者 需要在另一个字符串上跳多少。比如说这里我们选择让 表示已经匹配到了 的第 位，再走完一个 所能新匹配的字符数。

实际上，字符串长度是 级别的，我们可以直接暴力匹配预处理。

但是这样显然还不够，我们还能更进一步：反正你都处理出跳一次 的匹配的字符数了，不如再处理一下跳 次 的匹配的字符数。于是你成功的把时间复杂度降到了 。

参考代码如下：

T3。

其实本身难度并不是很大，首先处理出对于每一个节点两个人分别会怎么走，然后倍增处理出每一个节点两个人分别先走的情况下走 步两个人的开车距离增量以及新的位置。倍增就完了。

注意边界，可能换人。代码如下：

数据结构优化

动态动态规划

图论

最短路

floyd

floyd 是一种可以求全源最短路的算法，其时间复杂度为 。其思路比较接近动态规划。

具体地说，我们顺序枚举一个中转点 ，然后去更新每一对的 的最短路为 。这样子更新完之后， 实际上变成了经过 的点时的 之间的最短路。

一定要注意不要把 放到 里面枚举，因为这样子不满足 是经过 的点时的 之间的最短路。不过有研究表明把这样的循环执行三次也会有正确性？

代码如下：

spfa

spfa 的思路是逐步松弛，缩小点的最短路长度。

具体的来说，我们先将每个点的最短路长度设置为极大值，然后将起始点的最短路长度设为 ，将其放入队列中。

然后我们不停的取出队首，遍历其所有能到的点，如果有的点的最短路长度比从队首过来的更长，那就更新那个点的最短路大小。如果那个点不在队列中那就加入队列。

这个算法可以判断负环。显然如果一个点被更新了超过 次，那就一定有负环。时间复杂度是 的，随机数据下 ，但是实际上可以轻松卡到其上界限 。代码如下：

dijkstra

如果一幅图没有负权边，那么我们从小的向大的扩展一定不会错。因此，我们可以使用优先队列来维护最短路最短的没有扩展的点，并类似于 spfa 一样松弛其他的点。只不过因为没有负边权，所以第一次访问到就是最优解。代码如下：

johnson

johnson 是另一种可以处理负边权的全源最短路算法。他的思路是 通过将每一个点“抬高一点”，将边权转化为正权，然后处理。

我们引入一个物理上常见的概念，叫做“势能”。我们新建一个超级源点向每一个点连一条边，权值为 ，随后用 spfa 跑出到每一个点的最短距离 ，视为每一个点的“势能”。随后我们将 的边权重新标注为 。由最短路的三角形不等式可得这个边权是恒正的。

最后在求 的最短路时，。其中 是 diskstra 跑出来的虚拟距离。

为什么这样是正确的呢？我们注意到，在求 的最短路的过程中，势能的变化量永远是 ，和物理意义上的势能很像：势能绝对大小和选定的参考点有关，但相对大小与之无关，两点之间的势能差只与两端点有关，和中间怎么走的无关。

因此我们通过保证在任意两点之间的每一条路径的增加量相同的方式，保证了我们跑出来的最短路转化后仍然是最短路。

差分约束

差分约束可以用来求解形如 的不等式方程组。

具体的来说我们可以先通过调换顺序将不等号的方向同一，比如全部统一成 ，随后我们思考在最长路中的三角形不等式，发现 。形式一样。

于是 可以转化为 到 有一条长度为 边，然后随便找一个源点作起始点跑一下最长路就行了。

显然如果出现了正环，那么就无解，否则每个点的 就是一组合法的解。

最小生成树

prim

prim 的思路是加点。每一次我们选出和当前已选择的点集最近的点，并将它加入已选择的点集当中。

具体地说，最开始的时候，我们随意指定一个节点作为已选择的点集中的初始元素，并计算出每一个节点和他的距离。随后我们扩展 轮。每一轮我们找出距离最近的，加上他的距离，并将它纳入已选择的点集中。随后再用这个点去重新计算别的点的最短距离。这样扩展完之后 个点就都在已选择的点集中了。

时间复杂度 ，动用人类智慧的话就不清楚能做到多少了。

kruskal

kruskal 的思路是加边。每一次我们选出边权最小的边，并检查两个端点，如果两个端点不在同一个集合中，就把二者合并，并在贡献中加上这条边。否则不做处理。显然这个贪心策略不会出任何问题。

最近公共祖先

最常用的有 种解法：倍增，tarjan，dfs 序。

倍增法就是预处理出每一个结点的 级祖先。先将两个节点的深度调整一样，然后不停往上倍减着跳，最终二者相同的位置就是答案。参考代码如下：

tarjan 是一种可以做到严格线性的离线算法。通常情况下复杂度为 。

算法流程是这样的：我们先将询问同时记录在那两个点上，然后我们从根节点开始遍历。

每一次到一个节点 时，我们先去遍历他的所有子节点 并将 节点的并查集合并到 上。然后将 标记为遍历过。

最后检查 节点的所有查询 。如果 已经遍历过了那么答案就是 所在的并查集，否则不做任何操作。参考代码如下：

接下来是 dfs 序。dfs 满足一些神奇的性质，比如说 中深度最小的节点的深度恰为 的深度 ，如果 的深度比 小。

其实这个我不是很想证明，因为分讨一下 是不是 就 证明完毕了。这样子你就可以用 ST 表做到 查询了。

tarjan

tarjan 的思路并不复杂，我们先按照 序进行遍历，然后处理每一个边。具体的来说，我们给每个节点两个标记：。 记录他的 序中的编号， 则是在一定的规则下通过至多一条不在搜索树上的边能到达的 dfs 序的最小值。

强连通分量

强连通分量是针对于有向图说的。具体的，如果同时存在 的路径，那么 强连通，而一个强连通分量 就是一个满足 ， 强连通的极大子图。

那么我们在 tarjan 的时候具体怎么办呢？到每一个点 时，我们会将 和 均设置为 。首先，如果一个点 发现了一个没有遍历过的点 ，那么我们就可以先继续遍历 ，随后将 取为 。这一种显然没有问题。

如果发现了一个遍历过的点那就要分一下情况了：

如果这个点已经被标记在某一个强连通分量中了，那说明这个点无法到达自己，肯定和自己不是同一个强连通分量内的。

但是如果没有被标记过呢？那么有两种情况：一种是访问到自己的祖先了，一种是访问到了自己的子节点。总之我们发现我们的这个边不是树边，而且因为那个节点截至目前仍然没有被纳入强连通分量，所以一定能到达自己，可以更新。

说白了，在强连通分量下，这个规则就是双方互相可达。但是似乎上面的最后一句的“一定能到达自己”不是很说的走呢？

并不是的。当我们在遍历完了 的所有子节点之后发现 ，那么不难想到这个点及其子树中的所有点其实都无法逃出 的魔爪，否则就会更新到 中。因此没被更新就是可以访问到自己。

还差最后一个问题：我怎么知道该标记哪些点是自己这个连通分量内的？当 的时候，我们会去标记在 的子树之下而且可达到 的节点，

割边-边双连通分量

割点-点双连通分量

 

二分图

二分图是这一个图 ，可以分出两个点集 ，满足 且 或者 。

判定

有多种办法可以判定，常用的有染色法，扩展域并查集等。

染色法就是尝试给每个节点分配集合。显然如果 ，那么 ，换个集合仍然成立。

所以就随便钦定一个点在某个集合里，能分出来就有，分不出来就没有。

扩展域并查集类似，如果二者有就将 和 分别绑定一下。

最大匹配

就是给你一张二分图，问你能从里面选出多少边，满足这些边的左右部点都不重。

这个常用网络流中的 Dinic 或者匈牙利算法解决。

匈牙利算法就是不停的强制让某个点匹配上，如果某个右部点已经匹配上了就把他抢过来，直到成功匹配到没人的或者确实配不上。

网络流的话每一个左部点从源点牵一个流量一的，右部点连一个流量一的到汇点，中间的流量一就行。

霍尔定理

令 分别表示左右点集，那么定义 。也就是说 是左部点 所直连的右部点的集合。

再定义 。也就是说 是左部点子集 中存在点直连的右部点集合。

再约定 表示集合 的大小。

那么， 存在 向 的完全匹配。

显然和匈牙利算法的证明等价。必要性显然，充分性反证：

设G中不存在完全匹配，取 的一个最大匹配 ，则 中至少有一个点不在 上，且该点必至少与一条不在 中的边相连。

该边的另一个顶点若也为 非饱和点，则与 为最大匹配矛盾，若另一个顶点为 饱和点，则考察在 中与该顶点相邻的点，利用饱和点去考察在 中相邻的饱和点（交错地考察，即交错地通过 中的边和非M中的边），直至考察完毕。

由相异性条件知，最后必考察至非饱和点，此时出现一条增广路，又与假设矛盾（不是最大匹配），故充分性成立。refer。

扩展定理：

  1. 中最大匹配的情况下最多有 个点失配。
  2. 中每个点在匹配 个右部点的情况下仍然存在满最大匹配。
  3. 如果左部点 最多能匹配 个右部点，那么 存在满最大匹配。

证明的话，第一个可以让每个左部点同时连上 个赛博右部点，转化为原定理，得证。

第二个和第三个可以让第 个人裂成 份去分别和几个右部点连边，转化为原定理，得证。

但是解题是有技巧的，限制数是 级别的，我们需要去抓最紧的限制。也就是将有效限制个数缩到最小。从而求解问题。

网络流

FF-EK-Dinic

FF(Ford–Fulkerson) 增广思路

FF，即 Ford–Fulkerson 增广。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。

其中有一个概念叫做增广路，说白了就是所有边剩余流量大于零的路径。使用这条边显然可以使答案增加，但是直接贪心是错的。

接下来，我们进行反悔贪心。当我们给 这条边增加 的流量时，就将 的剩余流量减去 ，而将 的剩余流量增加 。

正如 OI-wiki 的一张图：

可以严格证明，这里略去。反正不考证明。其本质上就是 最大流-最小割 定理。

EK 算法

使用 BFS时，FF 增广表现为 EK 算法。其本质上就是将找出任意一条变成了找出最短的一条，每次使用 BFS 找出最短的增广路并增广。时间复杂度为 。时间复杂度劣，而且和 Dinic 难度大致相当，不附代码。

Dinic 算法

他的优化就在于他同时对多条增广路进行处理，具体的流程如下：

首先，对当前的图做一次 BFS，求出每个点的“深度”。

然后，进行 DFS。每次 DFS 时，记录当前节点和当前携带流量。随后，一直向深度大 的子节点分配尽可能多的流量，直到没有子节点或者自己流量用完。贡献就是所有被分配到的子节点的贡献之和。

这里还常用一个“当前弧”优化，其实说白了，就是之前已经被分配满的子节点以后不可能再分配了，因此记录一个已枚举位置就行。参考代码如下：

费用流

对于没有负圈的普通费用流，常用 SSP(Successive Shortest Path) 进行求解，思路类似于 FF，每一次找一条或多条单位费用最大/小的路进行增广。

负圈是指单位费用为负的圈。

注意费用流的时间复杂度是 的， 是最大流。可以被卡到 。

给出基于 Dinic 的参考代码如下：

上下界流

正如其名，原先只有上界的网络流也有下界拉！一篇较好的博客专讲基础上下界流。

存在性判定

对于每一个点，我们令 ，然后思考：

  1. 对于 的点，其入度的下界与出度的下界相同，也就是说这些边我们可以将上界重写为 ，仍满足流量守恒。
  2. 对于 的点，他若直接将上界重写为 ，则不满足流量守恒，出度过小。需要向超级汇点连一条容量上界为 的边。
  3. 对于 的点，他若直接将上界重写为 ，则不满足流量守恒，入度过小。需要从超级源点连一条容量上界为 的边。

此时，若从超级源点到超级汇点满流，则存在，反之不存在，由源汇点的流量与原图的流量守恒关系不难证得。

有源状态下的判定

从 向 连一条容量无限的边，就完美地将有源强转成了无源，然后就能做了。

最大/小流(有源)

我们还是先有源强转无源跑判定，判定完了之后记录 到 的最大流，删除 到 的边，然后分情况：

如果是最大流，就跑出 到 的最大流和开始的那个最大流相加得到结果。

如果是最小流，就跑出 到 的最大流和开始的那个最大流相减得到结果。

问什么正确呢？其实判定的本质就是强制流量守恒，也就是强制将上下界流改成普通流。

判定如果成功的话，那么所有的点都在同一个“势能面”上了，多余的就是在推流/反流。

比如针对两个的缝合体红石科技，我们可以这样写：

最大/小费用可行流

基于我们前面所讲的判定的本质就是强制流量守恒，我们不管在建出来的辅助图上跑网络流还是费用流，反正只要限定是最大流，就能对应出原图的一个可行流。

所以说，我们建出辅助图并且提前计算砍去下界少算的费用，辅助图的最大/小费用最大流就是原图的最大/小费用可行流。比最大/小流(有源)还少一步。

核心代码如下：

当然还是别忘了要给原图中的 建一条没费用的无限流。

模拟费用流

思路类似于手动消元，说白了就是利用建出来的图的性质进行针对性的优化，从而加速计算。例题1。

在这道题中，建模其实非常的裸，但是点数过大，完全不能跑费用流，因此需要手动最短路。

那怎么做呢？我们注意到原图近似是一个二分图，也就是说任意一条路径可以视为 ，任意多条 和 拼接而成的。第三段费用为 ，所以只用分别维护第一二段从每个 出发的最优边。

给出一份仅保留核心的参考代码：

例题2，同样非常好建模，但是不难发现边太多了，没法玩。

所以我们可以从最大流-最小割定理入手，算他的最小割。显然，因为图只有一层，即每一个城市对应的点都直连源汇，所以每一个点要么断源，要么断汇。

显然断汇的点仍有能力向后面的城市流货，而断源的不能，所以写一个 DP 出来就完了。核心代码如下：

2-SAT

记得我们曾经学过一个东西叫做“扩展域并查集”，说白了就是令每一坨 的区间中的点 对应表示 在 状态下与别的状态的联系。两个点在一起就认为两个点对应的状态必定同时满足。

那这玩意这么好用，能不能用到 2-SAT 上呢？

很可惜，需要改一下题才能用得到。把或改成异或就行了。

思考一下并查集的底层逻辑：两个点对应的状态必定同时满足。换言之，你只能加双向边。

然而 2-SAT 并不是这样的，他用的是或，也就是说硬性的约束条件是： 和 。都是单向的约束。

那我们思考一下这些限制中的强连通分量意味着什么？

显然，这意味着这些点对应的状态成立与否是相同的。同时我们就推出了如果 与 在同一个强连通分量内，那么必定无解。

强连通分量怎么求呢？Kosaraju 和 tarjan 你选一个吧。

当然了，2-SAT 只是一个最直接的应用。其实他给我们提供的是一种单向限制的处理思路，适用性比 2-SAT 本身要更广很多。

顺带讲两个常用优化技巧：

线段树优化建图

T1rt，弱化版。

翻译一下就是有 个数 和 个数 ， 次从 或 中选出一个数放入 ，排序后询问最小的 。

我们可以假定 。解法大概率会是二分答案。首先如果 ，那么这俩不能同时出现。以此来建边进行求解，复杂度 。可以过弱化版。

但是这样并不够优，究其原因是我们需要大量的向一个区间内的点建边。

而这，我们显然可以使用线段树优化建边来飞过去。具体方式可以看下面这幅图：

比如本来是 要向 和 两个区间建边。

现在我们可以对原本的 区间建一颗线段树如图：

那这时候 向 连等同于向 连，向 连等同于向 连。

显然这样下来每次要连的边数锐减至 条。总复杂度降至 。

比较核心的就是这坨：

前缀优化建图

T2rt。

题意简单明了，转化也非常的明显，但是问题也就出在了这里。

相当于说在同一个部分内的 ，一定要 到 连一条边。只要我把所有的点放在同一个部分内，你的边数就是 的。包炸的。

所以现在就是要去优化这个东西。我们不难发现，其实如果我们将这个部分内的点任意排序，那第 个点一定要向第 都连上边。

线段树优化建图不太好使，因为数据范围真的够大。但是思考如下结构：

不难注意到，如果我们给整个部分添加两个辅助的侧链基团，那么这时候指向 就间接指向了 ，指向 就间接指向了 。

非常妙，此题可解。我们称这种建图方式为前缀优化建图。比较核心的代码就是这坨：

二分图最大权匹配

从最基础的二分图最大权完美匹配讲起走：

最常用的是 KM 算法。他的思路是这样的：

首先我们假定原图存在完美匹配。然后，我们给每个点分配顶标 ，满足 。

我们再取出 ，满足 ，那么这时候，当 中存在完美匹配时， 就是答案。

正确性： 限定了每一条边都会具有的单调性，从而限定了整体的单调性（感性理解）。

算法流程：

首先令 。显然满足限制条件。

接下来尝试扩大 。在匈牙利算法中，从一个节点寻找然后匹配失败所遍历的树被称为交错树。显然，其中匹配上的边与没匹配上的边交错出现。

我们如果能在交错树上找到一条的路径，并将这条路径上的左部点 ，右部点 ，那么不会让交错树上原有的边消失，而且可能会出现新的匹配，从而增大 。

为了防止一次性减小过多， 应取为 ，其中 在交错树上， 不在交错树上。

不难发现这样操作，交错树原有边不变，而且至少多一个新的边。也就是说理论上最多会需要 轮。

那如果我们能将每次增广的时间复杂度降到 就可解了。

那很显然，如果我们使用 bfs 版的匈牙利算法，那么他每一次都是 的，然后再带上至多 次增广（ 个节点肯定已经有匹配了），总复杂度 。

代码如下：

然后我们偶遇了一个 trick: 抓大放小，rt。

其实这个名字起的听生动的。说白了，就是给更重要的那部分提权，使得它的影响力严格优于次要部分。

在这道题中，我们需要在满足最大匹配的前提下使得换位置的元素个数最少。

我们令没有交换位置的匹配权值大 ，并且原先匹配的贡献乘上 ，这时候对最大匹配的影响至少为 ，而总的不交换的贡献严格小于 ，从而优先满足最大匹配，然后满足最少交换。

最小树形图

主要讲三个东西：朱刘，tarjan，堆优化朱刘。

朱刘算法

朱刘算法思路很简单：不停的找环，把环缩成一个大点，然后接着找，直到形成一个 DAG。

更大的思路是除了根节点，每一个点尽可能选取最小的入边。显然在一个环中，我们不能直接抛弃最大的边，而是将连向这个环的那个边减去环上随后的那个边的权值。

也就是在反悔贪心。同时你也就可以反应过来为什么不能暴力选最大边。

所以你要是暴力模拟这个过程的话，你就得到了朱刘算法。代码如下：

tarjan/堆优化朱刘

他们的优化思路很简单，就是堆优化。

那么 tarjan 是怎么去求解的呢？它分为 收缩 与 伸展 两个过程。说白了就是先将整个图按照强连通分量缩成一个点，然后再根据记录的信息给把树重新建出来。

收缩怎么收缩呢？我们每一次任意选一个在堆中没有入边的的节点，并将它的最小入边加入到堆中。如果新加入的这条边使堆中的边形成了环，那么将构成环的那些结点收缩。我们不停的收缩，直到整张图被收缩为一个节点。

堆中的边总是会形成一条路径 ，由于图是强连通的，这个路径必然存在。我们每一次选一条最小入边 。如果 不在 中就将 定为 。如果在就形成了一个环。我们将这个环缩掉，显然还在最后。我们接着处理这个点就完了。

当然了，收缩的过程中需要记录一些信息。伸展过程是相对简单的，以原先要求的根节点 为起始点，对 到收缩树的根上的每一个环进行伸展。再以 的祖先结点 为起始点，将其到根的环展开，直到遍历完所有的结点。

一种实现：

堆优化朱刘相对而言可能会更好理解一点，真的就是给朱刘套上了和 tarjan 类似的可并堆优化。但是要注意处理指向环内的边。这些边对 tarjan 正确性没有影响，但是对朱刘有影响。给出完整的代码如下：

见的不多，而且目前来看遇到了基本上就挺板的，不再多说了。

仙人掌与圆方树

模板题显然就是一个狭义圆方树求仙人掌上两点之间的距离的板子题。

先说一下什么是仙人掌：仙人掌就是一种特殊的图，满足每一个边最多在一个简单环上。

我们会使用倍增 LCA 和树上前缀和来快速的求解树上的两点之间的距离。那如果我们可以将这个图转变成一棵树的话是不是就做完了？狭义圆方树就干了这么一点事。

那我们想一想这个圆方树都要处理一些什么呢？显然，成环的地方就是我们要重点考虑的。正是这些环，使得原先的图不是树。我们考虑如下结构：

肉眼可见的，我们通过添加一个点使得一个环变成了一个菊花一样的东西。我们处理完后一定是一棵树。而树上除了根以外别的点都一定是有父节点的。只要我们指定一个圆点为根节点，那每一个这样的环都会有一个最靠上的节点。

我们把这个节点视为这个环的起点，像任意方向绕着环转一圈，并把每个点的“距离”标记为第一次遇到他时走过的路程。接下来，我们把环的起点到这个环的方点的边权设置为 ，把这个环的方点到其他点的权值设为本环的起点到那个点的最短路的长度。

这意味着我们还需要处理这个环的长度。因为最短路是这个点的“距离”和环长减去“距离”的最小值。就像这样：

建出来了树了之后，分成两种大的情况：

第一种：两个点的 LCA 是一个圆点。这种情况相当的好，答案就是两个点在树上的距离。

第二种：两个点的 LCA 是一个方点。这意味着这两个点不停往上跳，最后跳到了一个环的不同的两个点上。这时候我们要处理出二者在环上的最小距离。于是我们之前记录的信息就发挥作用了。两个点之间有两个不同的种路径，一种是按照“距离”的行走方向的那段弧，长度为二者的“距离”的差，另一种是走另一段弧，长度是环长减第一种的长度。

至此，狭义圆方树求仙人掌上两点之间的距离讲解完毕。代码如下：

同学提出了一个问题，我觉得有必要讲一下：一个点有可能会在多个环里，为什么我们不需要记录这个点在每一个环中的“距离”和环长？

我们想一下我们询问的过程：首先如果 LCA 就是圆点的话那没什么影响，如果是方点的话那才会用到“距离”和环长。但是很显然，一个环的起点是骑在这个方点的上面的，也就是我们永远也不会用到一个环的起点在这个环上的信息。

而很显然，我们在建树的过程中，一个点永远也不会成为多个环的“终点”，而且最后一次处理这个点就是在他是“终点”的那棵树上。故不需要记录一个点在每个环上的信息。

那么，一个比较常见的应用就是圆方树上 DP，虽然我们不一定要把树真正的建出来。如题。

面对仙人掌的题，我们最基本的思路就是转化成树上问题求解。而很显然仙人掌本质上就是一棵树上面挂了一些边不相交的基环。

先看第一道题：没有上司的舞会。没错，这就是同一道题，只不过仙人掌上没有环而已。

为什么思考这个问题呢？因为这就是在推最基础的 DP 式子。显然：

。

再看第二道题：城市环路，不过请自己弱化一下，每一个点的人流量都是 。没错，这就是同一道题，只不过仙人掌上有且仅有一个环而已。

那我们想一下面对基环树时的套路呢？先随便选择两个相邻的点，指定他们的状态，然后进行 DP。

现在看回这一道题。现在“树”上有一堆子基环了，我们怎么办？

仙人掌的典型套路：把每一个环拆出来，逐个击破。剩下的非环边正常处理就完了。

所以面对基环树 DP，思考大抵是有点套路的：思考树上怎么做，思考怎么处理基环，套仙人掌找环处理环的板子。

代码如下：

数据结构

线段树

线段树是 OI 当中最常用的数据结构之一，务必认真掌握。接下来讲解的是比较常用的多种线段树及其变体，大致按难度排序。

这里有你没写完的东西，杂鱼...

ZKW线段树

很神奇的卡常用的线段树，但是支持面远远比不上普通线段树。

思路就是更改递归为循环。我们可以注意到，在线段树中，，因此，我们维护一个数组，使其也满足这样的性质，每次循环向上更新信息，就完成了。

查询的时候我们从区间的左右部分的端点外的一点开始操作。对于一个端点，当我们向内跳的时候，统计右儿子的贡献，当向外跳的时候，不统计贡献，直到两端点重合。

但是区间修改使用标记永久化，无法维护标记有顺序要求的情况。

参考代码如下：

并查集

普通并查集

并查集要维护的操作主要就是“合并”和“查询”。具体来说，他要能够支持将两个集合合并，并查询每一个元素在哪一个集合，比如判断二者在不在同一个集合中。

不难想到我们可以用类似于树的结构来实现这一点，具体的来说，我们要合并 所在的集合的时候，我们找到这两个集合的代表元素 ，并将其中一者的父节点设置为另一个。

但显然这样做如果给你整成链状的你就炸了，因此我们有诸多技巧来维护其时间复杂度正确。

第一种是路径压缩，也就是每一次查询完某个节点之后，我们将这个节点到他的代表节点这一条链上的所有节点的直接父节点设为代表。这样做时间复杂度均摊是 的。显然不是特别优。如果你再把他们按照大小合并，也就是将大小更小的那一坨的父亲设为更大的那一坨，时间复杂度进一步降至 。其中 是反阿克曼函数。

实际应用中，根本没人去卡那个 ，所以更常见的情况下你并不需要按大小合并。

还有另一种是按秩合并，也就是树高更低的合并到树高更高的上面。时间复杂度显然是 的。

扩展域并查集

又名种类并查集，思路就是拆点。举食物环为例题。

在这道题中，每一个生物对应有三种状态：是 A/B/C 类生物。于是我们将每个生物拆成三个点，比如说第 个生物就会被拆成三个不同的点 ，其中 表示 生物是 类生物这个陈述为真。而我们将并查集视为一种等价关系，即如果 在同一个集合内，我们就认为这两个命题要么都成立，要么都不成立。

那么对应到这一道题，如果两个生物是同类，则 ，， 应该分别进行合并。显然判断条件是 不能相互啃食，比如 或 等共计 个条件。二者相互啃食的类似，不再赘述。

可以给出核心代码如下：

权值并查集

这类并查集会需要维护多维的信息，比如和代表的实际距离。例题。

一般情况下，我们会考虑在重定向父亲的时候先去除父节点造成的影响，然后在路径压缩的过程中再逐步去合并信息。比如说当有一种信息是针对整个并查集改的的时候，我们会在合并的时候先将合并者的信息“减去”被合并者的信息，然后再在后面恢复过来。当然了，这个例题体现不出来。

一定要注意路径压缩时对信息进行合并的时候要记录好原先的父亲，不要随意拿着新的“父亲”去更新信息。

可以给出核心代码如下：

莫队

这绝对称得上是离线算法中的代表之一。话说，彼时的 界 问题并起，而我们的暴力却不能骗到太多分，于是 高手圈内流行起了一种快速处理离线问题的算法，并由莫涛整理，这种算法便被称之为莫队。后人便在此基础上加以拓展，统称为莫队算法。

算法的实现就是询问区间依靠 指针反复横跳。他要求我们能够在较优的时间复杂度内（一般为 ）用 的答案及状态转移出 或 的答案及状态。这时候，我们通过一定的方式找到一个较优的询问序列，使得其左右横跳的次数较为少。

这时候莫队的神奇重排询问方式发挥了作用。首先我们先这 个点顺序平均分成 个块，然后询问间排序时以左端点所在的块编号为第一关键字，右端点为第二关键字。这时候，右端点右移距离不超过 ，左端点移动次数在 的级别控制内，均有不超过 的理论常数（像黑塔那样左右乱滚）。于是总复杂度在 。

普通莫队

显然，上面的就是普通莫队。

以袜子为例，核心操作就是这样的：

特别注意，我们应尽量保证区间长度不为负，所以我们总是先扩展再收缩。

带修莫队

核心思路就是加上一维时间戳，因为 同在 的区间内，所以我们把 的排序方式强加在 上，然后 按照原来 的排序方式升序排序。当块长取 时时间复杂度为最优的 。但是一般情况下 同阶，所以时间复杂度常被视为 。

带修莫队有他的局限性。只支持单点修改，时间复杂度也已经只比暴力优了 ，可能要卡常。

回滚莫队

回滚怎么滚？为什么要滚？问题很简单，有的信息在增加或删除的时候很难在一个能接受的时间复杂度内处理出来。于是，我们就只让他扩展。

具体的，我们暴力处理完块内的询问后，块间的我们让他的左端点固定在 的位置，保持右端点单增，每到一个询问，记录当前的状态，让左端点扩展，到之后记录答案，然后快速滚回到 。

可以参见野史的研究的代码。

树上莫队

经典的序列问题上树。处理方式无非就两种：把树拍成序列；重链剖分吃掉这棵树。很显然，对于莫对这种喜欢像黑塔那样左右乱滚的神奇算法来说，第一个方式会更友善一些。

最终，我们选择了欧拉序，即进子树记录一次，出子树记录一次。这样子，我们可以通过一个点在序列中出现的次数轻松的知道他到底在不在序列上。

一般的，我们会将其拆成 和 两条链来处理。由于欧拉序的特殊性，对于不满足一者在另一者的子树内时，我们需要记录 。

然后就是类似于普通莫队的思路了。下面给一个树上莫队的代码：

笛卡尔树

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 构成。要求 满足二叉搜索树的性质，而 满足堆的性质。一般我们会需要构造一个笛卡尔树，编号为 的点权值为 ， 为给定的值。一般用栈解决。方法如下：

我们先按照下标顺序依次加入这棵树中，显然，为了维护二叉搜索树的性质，这个节点势必会在树的右链上。

这时候我们维护其堆的性质就行了。从下往上比较右链节点与当前节点 的 ，如果找到了一个右链上的节点 满足 ，就把 接到 的右儿子上，而 原本的右子树就变成 的左子树。

复杂度线性。可能视情况会需要树上 ，四毛子等。

树套树

首先给出警告：树套树时空常数大，代码复杂，一定要静下来调，线段树中不要记录当前节点的区间端点，在函数中下传！

其实修正一个对树套树的认知错误：树套树实际上只有最内层在维护实际有效信息，外层只是为了减少内层维护次数，从而降低复杂度，而不做信息的合并。

在这基础之上，就不容易出错了。主要补充一些技巧。其中第二个板块有线段树套平衡树的参考代码。接下来讲一下相对好写而且支持面较广的树状数组套线段树。

这里有你没写完的东西，杂鱼...

线段树二分/树状数组倍增

前者就是线段树上二分。因为线段树是分治型结构，所以复杂度单 。方法就是在每一个节点选择往左/右子树走。

后者如其名，因为树状数组是倍增型结构，所以复杂度单 。方法就是跳 个， 越来越小。这时候，前面的贡献不会被重复统计，达到效果。

多树二分

不难注意到，在树套树模板题中，我给出了如下代码：

那么请看第 到 行，这一部分就是为了防被卡。仔细看会发现这个操作是 的。这时候就需要多树二分了。

多树二分，一句话说，就是将会涉及到的线段树树上的节点给全部放一起，然后一起二分。这时候，节点个数是 级别，二分是 的，整体双 。以 lby 的代码作为实现思路：

严格次小生成树

还挺简单的，能直接口胡出思路来，就是建出最小生成树，然后在上面换边。只涉及到了倍增和最小生成树相关的。给出相对简短的实现：

整体二分

正如其名字，我们将所有的询问放到一起来二分，这样可以节省中间重复的判断的时间。思路很简单，结合题目去想一下能不能高效维护就是了。

例题核心代码：

只是题必须满足以下性质：

  1. 询问的答案具有可二分性
  2. 修改对判定答案的贡献互相独立，修改之间互不影响效果
  3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
  4. 贡献满足交换律，结合律，具有可加性
  5. 题目允许使用离线算法

陈丹琦分治

CDQ 分治其实更像是一种思想。CDQ 的经典例题处理的是三维偏序问题，即满足 的整数对 的个数。

这个东西，一看就可以 KDTree（大雾）。

显然不优，CDQ 可以做到 。

核心思路就是先按照第一维排序，随后归并排第二维的序列。归并的时候，左部点仍然满足 比右部点小。此时我们依次归并 ，当 来自右部点是计算比该点 值更小的已归并的数量之和，这可以用树状数组快速维护。

求解完成。模板题核心代码：

可以求解类似动态逆序对，二维数点等的部分问题。

但是这只是非常狭义的 CDQ 分治。我们现在要去研究其核心思想，也就是对于更广的一类题目，我们到底怎么处理：

从上述过程中，我们可以窥见 CDQ 的核心思路。假设现在我们要求出 的贡献，那么我们将其分成两半 和 ，然后统计 对 的贡献。

事实上，中间贡献的计算不一定是像三位偏序那样的简单的数据结构，它可以是线段树，平衡树，kd-tree，甚至是另一层 CDQ 分治！

一个典型的例题是四维偏序，但是我们换一个略有挑战性的TATT进行讲解。

在经典的三维偏序中，我们每一次二分的时候可以视为将左区间的 拍扁成了 ，右区间的拍扁成了 。在保证 的前提下，只有 能对 产生贡献。

在四维偏序中，我们可以使用类似的思路：我们在第一层将 拍扁成 ，然后在第二层将他进一步拍扁成 ，然后只统计当 时 对 的贡献。仍然使用树状数组。

下面给出TATT中的 CDQ 部分的参考代码：

重链剖分

重链剖分是树链剖分中最强大也最常用的一种。重链剖分是这样的：

对于每一个节点，我们选出他的一个儿子，满足以这个儿子为根的子树大小不比别的子节点小。我们称这个儿子为重儿子。其他的我们称为轻儿子。连接重儿子和父节点的边称为重边，其余的称为轻边。这时候，一个极长的只由重边构成的链称为重链。显然一棵树会被剖分成许多的重链。

随后我们使用数据结构对重链进行维护。一种常见的做法是使用线段树。不过这要求链上的节点的编号是连续的。我们按照优先遍历重儿子的方式对整棵树上的节点重新标号为其 dfs 序。这时候同一重链上的节点的编号连续，同一子树内的结点的编号连续，因此我们可以快速维护部分对路径或子树进行修改或者查询的操作。

有点抽象，还是举个例子。比如模板题，他要求维护子树加，子树求和，路径加，路径求和。确实模板，我们主要说一下路径的维护方式。

树上的任意一条路径本质上都是一堆重链的部分被一些轻边串了起来，同时也是 和 串起来。因此，我们可以考虑通过不停的跳重链的方式维护路径信息。

具体的，如果 还不在同一条重链上，我们就选择链顶深度最大的那个节点去跳，先合并链顶到那个节点的信息，然后让那个节点跳到链顶的父节点。当 到了同一个重链上之后，我们就可以直接合并 的信息。

代码其实挺简单的，但是我们还没有证明时间复杂度。

我们发现一个性质：我们每跳一次轻边，以当前节点为根的子树大小至少能够 ，因为有重儿子压着你的嘛。也就是说，一个点只要是在向上跳，那就至多只能够跳 次。跳到 上其实也是同理的。

所以单次操作时间复杂度就是 的。核心代码如下：

长链剖分

虽然和重链剖分一样都是树链剖分的一种，但是面对的主要问题却很不一样。长链剖分主要是解决一些和深度相关的 DP 问题。长链剖分是这样的：

定义长子节点表示其子节点中子树深度最大的子结点。定义短子节点表示剩余的子结点。从这个结点到长子节点的边为长边。到其他轻子节点的边为短边。若干条首尾衔接的长边构成长链。

它本身并不是很适合维护链修改操作，毕竟他最多会跳 次短边，远远劣于重链剖分。但是对于深度相关的 DP 问题却有着很大的优化。比如这道题：

DP 式子其实非常好想，难就难在转移。你可以通过线段树合并等等复杂的技巧去维护，但是这是不必要的，我们可以用长链剖分用简短的代码做到线性复杂度。

具体的来说，我们让一个节点直接继承长儿子的 DP 数组，并在前面插入一个数 ，表示在相对深度为 的位置有且仅有一个节点，然后暴力合并所有短儿子的 DP 数组。做完了。

没错！做完了。我们分析一下时空复杂度。

首先对于每一个长链，我们仅在链顶的时候被暴力合并一次，而且显然有效的位置最多只会有其长度那么多个，因此合并的时间复杂度是 的。空间呢？我们发现我们可以通过指针预留空间的方式，让一整个链完全基于同一个数组进行修改，不同的链也可以通过相应的偏移给别的链预留足够的空间，从而空间也是线性的。

代码如下：

有的时候不得不佩服一下发明这种简洁美丽的算法的人。这才是数据结构的美之所在。

平衡树

平衡树本质上多是一棵 BST，但是将值顺序插入 BST 会得到链，所以平衡树要通过各种技巧维护 BST 的树高。最常见的操作是旋转，也就是调整父子关系的同时维护 BST 的性质。

这里介绍两种最为常用写的平衡树和一个替代品。一个是 Splay，一个是 FHQ-Treap。主要会围绕两道模板题进行讲解。

Splay

Splay 采用的是旋转的思想，而且比 Treap 本体的旋转操作更为单一，只有上旋操作，就是顶替父节点。

首先，我们会需要一些最基本的辅助操作。一个是 bel，用来判断某一个节点是不是父节点的右子节点。一个是 pushup(pup)，是用来更新节点信息的。

接下来是重头戏：旋转操作。这个是用来保证时间复杂度的。作为一颗 BST，旋转操作需要保证中序遍历不变，而且节点的信息能够及时更新。

Splay 中，最基础的旋转操作是单旋，将是让某一个节点 向上顶替他的父亲 。细分的话其实可以分成左旋和右旋，跟 Treap 似的，如图：

但是我们要善于发现操作的共性。这两种旋转本质上都在做如下步骤：

  1. 找出父节点，爷节点，与父结点方向相反的子节点，也就是这样（注意严格区分方向）：

  1. 在父节点原先挂自己的地方挂上那个子节点，调整相应父子关系，合并信息。
  2. 在自己原先挂子节点的地方挂上父节点，调整相应父子关系，合并信息。
  3. 在爷节点原先挂父节点的地方挂上自己，调整相应父子关系，合并信息。

写出来代码就长这样：

还没有完，如果你就一直这样把一个节点旋上去的话，时间按复杂度是不对的。最简单的一个例子就是一条方向相同的链，旋完之后正好变成了换一个方向的链。

所以我们引入更加神奇的双旋。也就是说我们两次两次的转。如果本节点到父节点的方向和父节点到爷节点的方向相同，就先转父节点。再转自己，否则连续两次旋转自己。我们发现这样之后，自己一定有两个子节点，分别是原先的父节点和爷节点。感觉树高似乎就有保证了。

接下来是 Splay 中最核心的操作：splay。它的作用是将一个节点旋转到另一个节点下，或者直接转到根。在这一步，我们就是要不停的调用双旋，直到转到想要的位置。也请请务必保证每次向下访问节点后，都进行一次伸展操作。这是它的时间复杂度能够得到保证的关键步骤。严格证明需要势能分析，而且较长，这里不做阐述，具体的可以参见 OI-wiki 上的证明。代码如下：

最基础的操作就搞定了，剩下的就是针对题目的操作了。具体参见以下的对普通平衡树的代码：

没有完，splay 树的结构非常灵活，它也可以用来处理区间翻转类的问题。但是暂时没有去研究，毕竟在这方面他的表现比不上 FHQ。可以在下面的第一个网址找到动态演示。

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

FHQ-Treap

FHQ-Treap 又称无旋 Treap。从名字就能够看出来这是一种不带旋转操作的神奇平衡树。但是这个名字看着又眼熟又觉得怪怪的？没错，Treap 是 Tree 和 Heap 的合成词。这样一颗树有两个核心键值，一个是我们 BST 维护的本体信息，一个是用来保证树高的数值。

Treap 满足第一个键值的中序遍历是有序的，也就是满足 BST 性质，第二个键值父节点大于任何一个叶子节点，也就是满足堆性质。

他的思想也很简单：既然在随机数据下 BST 的期望树高就是 的，那我要是引入一个随机的键值，是不是他的期望树高也差不多就是 的呢？没错，他用做堆的键值是随机生成的。

显然前面介绍的 Splay 的旋转操作可以维护这两个键值的信息，那他是怎么把旋转操作抹去的呢？

通过分裂与合并！这两个是 FHQ-Treap 的最核心的操作。分裂时按照第一键值的大小分成两部分，合并时按照第二键值的大小维护堆性质合并成一部分。

其实差不多就讲完了，剩下的就可以看代码了。毕竟他的核心思路相较于 Splay 简化了不止一点。

分裂：

合并：

其实和线段树的分裂和合并是比较像的。总的代码如下：

不仅如此，因为他在合并的时候完全不关心第一权值的大小，分裂的时候也可以按子树大小进行分裂，所以它可以快速维护区间位移，翻转以及常见修改等的问题。效率也比较高。

按子树大小进行分裂本质上就是将区间裂成了两半。其中第一半的大小完全可控。因此区间的所有操作都可以认为是将区间分裂出来，打上标记之后再放回去。其实没有特别本质的差异。对于一个稍微复杂的题的代码如下：

李超线段树

要求在平面直角坐标系下维护两个操作：

  1. 在平面上加入一条线段。记第 条被插入的线段的标号为 。
  2. 给定一个数 ，询问与直线 相交的线段中，交点纵坐标最大的线段的编号。

我们发现，传统的线段树无法很好地维护这样的信息。这种情况下，李超线段树便应运而生。

区间修改，最常见的办法就是给每个节点一个懒标记。对于每个区间，维护在 处取值最大的直线的信息。

现在我们需要插入一条线段 ，在这条线段完整覆盖的线段树节点代表的区间中，某些区间的最优线段可能发生改变。

考虑某个被新线段 完整覆盖的区间，若该区间无最优线段，则该线段可以直接成为最优线段。

否则，设该区间的中点为 ，我们拿新线段 在中点处的值与原最优线段 在中点处的值作比较。

如果新线段 更优，则将 和 交换。那么现在考虑在中点处 不如 优的情况：

  1. 若在左端点处 更优，那么 和 必然在左半区间中产生了交点，递归到左儿子中进行插入；
  2. 若在右端点处 更优，那么 和 必然在右半区间中产生了交点，递归到右儿子中进行插入。
  3. 若在左右端点处 都更优，那么 不可能成为答案，不需要继续下传。

由于仅有一个交点，所以两边子区间最多会递归一个。复杂度 。但是需要注意，因为每一次我们都需要对全覆盖的区间都进行修改，而这样的区间是 级别的，因此单次修改的复杂度为 。

查询 答案时，从根走到 节点记录的所有最优直线在 时取值的答案极值即为所求。这里是运用了标记永久化的思想。查询的复杂度就为 。

特别需要注意，对于不优的三种情况的讨论中，如果二者在端点同样优，那么一定要视为 更优。这样才能保证对于两个重复的线段不会一直走 操作，从而导致时复错误。

核心代码如下：

Q1:为什么一定要在路径上取 而不是一直走到底，返回最底部的状态？

标记永久化。

实际上，对于一条线段，他在中点最优常常意味着他在全局都是比较优的。尤其是对于第一次存入的区间。

也就是说，对于相当大的一部分线段，他其实是整个区间的子区间的最优解。但是如果真的更改整个子树，其复杂度退化为 。

所以说，与其更改整个子树，不如直接标记永久化，最后再在这些可能的最大值中刨出真正的最大值。

Q2:李超线段树合并细节？

其实不难想象，对于李超线段树这种有永久化标记的树，其合并方式不太一样。

不过，对于同一层，其实我们只需要将其中一个的最优线段合并到另一个当中，然后递归合并就行了。

特别需要注意一点，对于【模板】李超树合并，其时间复杂度实际上是 的。这一点可用势能分析得出。参见第一篇题解，非常玄妙。连官方题解都分析错了。

典型应用：

  1. 优化 DP，也就是动态维护斜率优化 DP 的凸包，支持任意地方插入。
  2. 李超线段树合并，主要也是优化 DP，主要是在对于整个子树的最优信息的合并。

例题：T0:P4097,省选/NOI-,模板题；T1:P4254,省选/NOI-,模板题；T2:P4655,省选/NOI-；T3:CF932F,省选/NOI-；T4:P4069,省选/NOI-。

动态树

动态树，顾名思义，这种树是动态的，可能删边或加边。 可以动态维护其中的连通性信息，路径信息，子树信息等，以模板题为例。

首先，你需要学会：文艺 Splay 树，实链剖分。

实链剖分？没见过。但是，我们可以管他叫乱链剖分，因为他确实是随便选一个儿子当成实儿子，其余的当成虚儿子。

这有什么用呢？他非常的灵活。不像重链或者长链一样改一个上面全得改。

剖分完了，然后呢？然后，我们将被一堆实边连到一起的树甩到文艺 Splay 里面，构成一颗树。

那虚边怎么办？我们采用一种神奇的方法：认父不认子！我们正好满足了高效维护虚边和只向上移动的需求。

又因为我们有一堆的 Splay 树，构成了一个森林，我们管这个森林叫做辅助树。一个辅助树对应原森林中的一棵树。

那辅助树需要满足什么性质呢？每一个 Splay 的中序遍历满足按照深度排序。这样，我们就完成了原森林到辅助森林的转化。

我发现自己常常突然就困惑一颗 Splay 怎么就能维护一棵子树的...。其实问题也很简单。永远记住一颗 Splay 树维护的是一条实链而非子树或者路径，这条链上的点深度单调递增，而且恰好就是 Splay 树的中序遍历。Splay 维护的是一条链而不是一颗树，或者一条有上有下的路径，他只管好自己的链就完了。

接下来，就是实现了。Splay树中都有哪些函数和变量呢？

首先说最基础的 pup，pud，rot 和 splay。

pup 即 pushup，将子节点的信息上传上来。这里，我们需要维护每一个节点在 Splay 中的子树中的所有结点的异或值。

pud 即 pushdown，将旋转标记下传，毕竟是文艺 Splay 嘛。

rot 即 rotate，将一个节点向上旋转，Splay 的基础操作。但是要做一定的修改。

首先，一定要严格判断父节点是不是当前 Splay树的树根。如果不是，一定不要让祖父认这个儿子，因为认父不认子只出现在虚边，而一颗 Splay 维护的是实边树。

其次，一定要严格判断子节点是否存在，不要让 有了父节点。

别的大致没有什么好说的，注意先 pup(fp) 再 pup(p)，因为这时候 已经成为 的子节点了。

splay 就是你想的那个函数，但是因为在 中只涉及到了将一个点转到当前 Splay 树的根节点这一种操作，所以省略掉了第二个参数。不过需要注意的是因为存在区间翻转，所以在 Splay 之前要先从根开始下放翻转标记然后再 Splay。

然后说一下 特有的函数。

nor 即 not_root，判断一个节点是不是当前 Splay 的根节点。判断方式很简单，看他是不是父亲的儿子，因为认父不认子。

access 是 的核心操作，它会将 在原树中到根节点的链变为实链。可是我们不是不维护原树吗？

其实我们仔细想一下，因为他们在同一个实链当中，所以他们在 access 完了之后只会在同一颗 Splay 中。所以我们只需要将路径上的 Splay 间的边设为实边就行了。

具体的，我们不停地将当前节点旋到树根，让父亲认这个儿子（原先的儿子因为认父不认子而自动降为了虚儿子）为右儿子（中序遍历满足深度递增），再将节点重定向到父亲上就完了。

swn 即 swap_node，即将这个节点区间反转。为什么会用到呢？下面会讲。

ron 即 rotate_node，将这个点到根节点的区间反转标记下传。

mkrt 即 make_root，将这个节点设为原树的根。也很简单，打通他和根节点之间的路径（access），旋到树根，区间反转。

为什么区间反转呢？中序遍历按深度递增。反转之前他只会是整个 Splay 中最下的节点，旋到树根后所有节点都在他的左子树，区间反转一下它就成为最低的节点，也就是根节点了。

fnrt 即 find_root，找他在原树中的根。我们只需要 access，splay，然后边下传标记边向左子树走，最靠边的就是根节点。

tlnk 即 to_link，就是用一颗 Splay 树专门来维护 之间的链。显然我们只需要 mkrt(l)，access(r) 之后 splay(r) 就行了。

link 就是 中 对应的操作。他就是连接一条 的边。我们只需要让 成为原树树根，然后 就行了。

cut 就是 中 对应的操作。他就是断开 的边。我们只需要让 成为原树的根，将 转到 边上，不认父不认子就完了。

剩下的两个就是对题的函数了，不用管他。这个真的需要背板子，背什么呢？这些：

如果想要背的更精简的话，可以从 access 开始自己长一个 LCT 出来。access 既要求调用前面的所有最基本的小函数，同时也是后面多是操作的基础之一，逻辑清晰而不那么容易写漏。代码如下：

应用类题单可以参见这篇博客，更底层的介绍也可以在这里看。

当然了，动态树是图论当中博大精深的一部分，和网络流类似，他也有大量的变种与维护技巧。下面将会管中窥豹，浅浅地介绍两个常见维护要求与相应的常用的应对技巧。

先看第一道题，概括为短边加连边，链加链最大。

其实 LCT 处理这种链修链查的动态树问题的话还是比较容易的。因为我们有 tlnk 操作，可以直接提取出来一条链，所以唯一的区别就是多了一个 tag，上下传的时机和翻转标记一样一样的。省略部分重复的代码如下：

但是当他要处理一些子树相关的统计的时候就没有那么容易了。比如这道题。可以简述为有加断边，改点权，查询连通子树最大点权。

事实上这一类问题的一个常见处理方式是专门设一个变量什么的统计虚儿子的信息，然后一并合并到统计子树的变量当中。

比如在这道题当中，我们可以专门维护一个 multiset 记录虚儿子代表的子树的最大值有哪些值，在 pushup 的时候和 mx[lson],mx[rson],v[p] 一起比较，动态插入删除就行。当然这也可以用两个优先队列做到相同的效果。

另外一提，像这道题的树的结构是相对固定的，我们可以用一种神奇的科技做到不带翻转操作进行增删边。具体的来说，我们可以提前指定父亲，也就是将 LCT 的相对动态的结构静态化。那么当你需要删除一条边的时候，你只需要先把他 access 并 splay 上去之后和左儿子互不认就行了。需要重新加回来的时候，就先将父亲 access 并 splay 上去，然后互认父子即可。

代码如下：

快速傅里叶变换

快速傅里叶变换还是太超模了。FFT 可以在 的时间复杂度内解决两个次数不高于 次的多项式的卷积。

首先，多项式最直观的表示方式是系数表示，但是 FFT 转而使用点值表示。对于一个 次多项式，可由 或更多个不同点的位置确定。这一点在此不作证明。

接下来，我们假定我们有两个 次的多项式 和 ，那么假设我们算出了 个点的值，分别为 和 ，那么 必过 。

就是这么一坨东西。显然，我们如果能够快速的在点值和多项式之间转化，那么我们就能够快速的求出两个多项式的卷积。问题就在于我们如何在二者之间快速转化。

神奇的地方就在于此。让我们做一个小小的变化。假设 表示 中 的偶数次方项之和， 表示 中 的奇数次方项提出 的公因数之后的式子，那么不难发现， 都只剩偶数次方项了。

这有什么呢？不难注意到，。初现端倪，我们递归此过程的话，是不是就可以做到 了呢？

似乎并没有，接下来你在求 的时候，你无法再使用正负点对来加速了，毕竟 的平方一定是恒正的......吗？

不一定是啊！你回忆了一下你不知道学没学过的复数，想到单位根正好满足这个要求。

最底层的时候我们求最底下的那个多项式（其实已经只剩单项式了）在 ，其中 取值范围为 。

那么你再观察一下，当 的时候，。也就是说，只要我们能让 是一个形如 的数，我们就能一直将这个过程进行下去。

那很显然，不足的位我们直接补 就完事了。

于是我们成功地将多项式在 的复杂度内变为了点值表示。

那么，怎么从点值变回多项式呢？

我们这样来看：FFT 实际上是快速的求出了 。那么经过一些神奇的推导，我们很难发现：。这一点可以通过直接的数论推导或者 FFT 中各步骤对应的矩阵乘法形式通过逆矩阵证得。

此时你又定睛一看，发现如果你令 ，那么 ，FFT 不就能求了吗？

因此，我们求出了两个多项式的卷积，复杂度 。

更多优化与应用在 NTT 讲。

快速数论变换

也算是为数不多的几个完全不需要掌握其所以然的算法了。可以从 FFT 那里变过来。

NTT 本质上就干了一件事：把复数映射到了整数集上，然后接着干。

怎么映射呢？原根。对于质数 ，且 ，那么原根 满足 。此时我们可以将 看作 的等价。

说白了，在模 意义下可以认为 。常见的 有 。

所以你只需要把代码中对应的那些位置替换一下就行了。

若干优化

逐步看。这是 FFT 比较劣的一个版本，模板题要跑 2.77s。

我们知道，复数的运算其实很耗时间，所以能少计算一次，尤其是乘法，会有一定的优化。所以我们将 tv * vr[i] 的结果存下来。这样就能优化到 2.65s。代码如下：

这不是重点，接下来要介绍一下非递归版的 FFT。

我们在运行的时候会不停的涉及到交换位置，导致最后算出来的东西出现乱序，根本用不了。但是如果我们预先将这些位置预先换了，是不是就没有那么多问题了？

确实。不过一个悲催的问题是我没有搞懂他为什么是代码中的那个位置。所以死记吧。这样能直接优化到 1.65s。代码如下：

应用

重要的是卷积形式。这又是什么呢？就是形如 的式子，其中 均不与 相关。显然从卷积的暴力计算方式来看，就不难发现 对应的系数就是要求的 。

于是，只要你能化出卷积形式，就可以用 FFT/NTT 做掉了。典型例题有第二STL行。EG：

所以就能得出核心代码如下：

prufer序列

这个也是相当的重要的。Prufer 序列可以实现无根树和值域为 的长度为 的整数序列之间的转化。

那么怎么转化的呢？先看第一种：树转 prufer。

每一次我都选择当前编号最小的叶子节点，将它的父节点的编号存到序列中，然后删掉这个节点，直到只剩下两个节点。

显然，用堆可以 做。但是如果你仔细想一下就会发现，每删一个点最多再加上一个点。因此我可以顺序枚举点，如果能删就一直删，直到非叶子节点或者编号比初始位置大。时复 。

再看第二种：prufer 转树。

首先由于 prufer 序列的一个非常显然的性质：每个节点在序列中出现的次数就是其度数减一。所以我们每一次选择编号最小的度数为 的节点与当前枚举到的 prufer 序列中的点连接起来，将二者的“剩余度数”减一。当 prufer 序列枚举完后就剩下了两个点，连起来就行。

但是由于和树转 prufer 类似的构造方式，显然仍然可以用类似的方式来线性构造。

有什么用呢？首先他明显证明了 Cayley 定理： 个节点的带标号的形态不同的无根树有 个。

其次，按照 LZJ 所说，会有一些题要用这个序列和一些数据结构搓一下，但是似乎到现在为止他也没有给出相关例题，就先放着吧。

可并堆

斜堆

斜堆应该是非常好实现的一种可并堆。假设我们有 个堆，每一个堆初始大小都是 的。

斜堆每次合并时先比较一下两个正在合并的堆的堆顶，视情况选取更小的那个堆，并将那个堆的左儿子/右儿子和另一个堆接着合并。随后直接交换左右儿子。非常潦草，但是操作均摊下来就是 的。感性证明不难，不会严格证明，想了解的看这里。模板二代码如下：

随机堆

更潦草了，直接在合并的时候随机向左子树或者右子树合并，期望树高是 的，对吧？

左偏树

这个稍微科学一点。我们定义一个节点的 为其到子树中最近的外节点所经过的边的数量。空节点的 。我们让这棵树保持左偏，即每个节点左儿子的 都 右儿子的 。因此左偏树每个结点的 都等于右儿子的 。

所以一种常见的写法是将要合并的和右儿子合并，并且判断满不满足左偏性质，不满足就交换一下。复杂度证明参见这里。

需要提醒一点，上面三种树理论上讲深度可能达到 ，找一个点所在的堆顶要用并查集维护，不能直接暴力跳父亲。

线性建堆

这个会在图论的最小树形图中遇到，所以还是要讲一下。

其实很常见的写法是将要用到的数全部放到一个数组里，然后类似线段树建树的方式给他递归下去建树。

不过我们还有另一种略短一点的写法。我们将所有的值全部建出节点来，放到一个队列里面，然后不停的合并队列的前两个元素，直到只剩一个元素。

虽然还是很潦草，但是理想状态下队首的大小是 。懂吧？如果不完全是 形的数差的也不会太大。

kd-tree

K-D Tree 是一种可以高效处理 维空间信息的数据结构。

先讲建树：

k-D Tree 具有二叉搜索树的形态，二叉搜索树上的每个结点都对应 维空间内的一个点。其每个子树中的点都在一个 维的超长方体内，这个超长方体内的所有点也都在这个子树中。若当前超正方体只有一个点，就返回这个点，否则的话轮流选一个维度，并将这个维度的中位数作为这一维的分割标准。按照这一维的大小分成左右两部分。Eg.:

轮流选择多个维度可以使得树高降到 。正确性显然。查询复杂度是 的。可见效果拔群（雾）。

那如果我们要修改呢？一种常见但是时间复杂度错误的写法是替罪羊树，这样会使得树高降到 级别。而查询复杂度是建立在树高为 的基础上的。

有一种复杂度正确而且相对好写的方法叫做二进制分组。具体的，我们将这些树分成大小为 的许多棵树，查询的时候每棵树查询一次，然后合并结果。如果某一层的大小超了就不停向上合并。均摊 。可以证明查询复杂度仍然是 的。

模板题参考代码如下：

不得不说真的非常屎山，考试的时候最好不要遇到。

数学

质数的判定

暴力

对于一个合数 ，他一定会有一个 以下的因数，由唯一分解定理，正确性显然。所以我们检验 到 是不是 的因数就完了。不给代码了。

埃氏筛

一个质数除自己以外的其他倍数一定是合数。所以我们从 开始枚举，如果这个数没有标记就把他的其他倍数全部标记了。复杂度是 的。代码如下：

欧拉筛

又名线性筛，真的是线性的。埃氏筛的复杂度不是严格线性，问题就在于同一个合数会所有的质数给标记。线性筛可以做到只被最小的质数标记。

我们思考对于每一个合数 。那么他其实只有可能被 给标记到。这正是埃氏筛。但是因为有 i % p[j] == 0 -> break，所以说当 的时候其标记到尝试会被更靠前的质数给禁用掉。所以只有在 的时候才会被标记。从而是线性的。

代码如下：

Miller–Rabin

如果 为素数，则 ，设 为奇数，则以下两个命题至少有一个成立：

这个定理的逆定理并不成立，但是如果你取的 足够好，并且多测几组，那么总能将复杂度降下来。事实上如果你取 ，那么它在 long long 范围内的正确率是 。

代码如下：

卡特兰数

卡特兰数非常常见，可应用于以下问题：

  1. 有 个人排成一行进入剧院，入场费 元。其中 人只有一张 元的钞票， 人只有一张 元的钞票。请问有多少种方案使得剧院总有 元钞票来找零。
  2. 有一个大小为 的方格图。左下角为 ，右上角为 ，每次只能向左或向上走且必须满足所有经过的位置 满足 。
  3. 在圆上选择 个点，将这些点成对连接起来使得所得到的 条线段不相交的方法数。
  4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数。
  5. 一个栈中顺序放入 的不同的合法出栈顺序数。
  6. 个节点可以构造多少个不同的二叉树。
  7. 个 与 个 排列成数列 ，求满足 的 的个数。

不难发现， 是完全等价的， 是完全等价的。实际上， 的递推式是完全一样的。我们可以得出若干不同的式子：

。

。

一般可以认为边界条件为 。

为什么是这样的呢？先看第二个式子。显然， 就是不考虑 的从 到 的方案数，而 就是不考虑 的从 到 的方案数。这俩有什么联系吗？

我们想一下，如果一个路径不合法，那么他一定会在某一步走到 。这时候，我们将他在 到 的路径反转一下，就像这个样子：

神奇的事情发生了：一个到 的不合法路径被映射到了一个到 的路径。随后，不难证明，每一个不合法路径都会唯一对应一个到 的路径。那每一个到 的路径都唯一对应一个到 的不合法路径吗？

是的。我们直接让他在第一次越过 线的时候就翻折，显然一一对应。证毕，解决 。

第二个式子显然能够推到第一个式子，不用多说了。也可以证明出来第三个式子。那第四个呢？

从 或 都能够推出这个式子。 从分治的角度去想， 从树形 DP 的角度去想都能得到这个式子。证毕，解决 。

那怎么证明这两个式子是恒相等的呢？数学归纳法是一个比较容易想到的方法。读者自证不难？

典型例题：卡常难数。

裸题123456。

应用12。

拓展12。

威尔逊定理

( 为质数)。可以用逆元两两配对证。

一般情况下不考，要考则考的足够板。主要的作用可能就是优化对这类数的快速幂操作的一个 ，或者这道题的用途。主要是第二个。

错排列

简述思路：枚举每个数位置合不合法， 容斥，进一步发现数量相同贡献相同，压缩贡献计算得到 ，进一步化简为 。

记个结论就完了，这东西不太能考的不板。

圆排列

，主要是记住他的最后除掉多统计部分的思想，解决其他类似问题。

多重集排列组合

以下按照这样的方式记录一个多重集 。 中共有 种不同元素 ，其中第 种有 个。该集大小为 。

用到最后除掉多统计部分的思想。全排列大小为 。

如果是普通的排列组合，则需要用到容斥的思想，如下：

对于其组合，先考虑这么一个问题：有 个篮子，把 个元素扔进去的方案数。这种问题常见的处理方法就是隔板法。显然答案就是 。

接下来，我们考虑对于一般的情况。一般的情况其实和上面的问题的本质区别就在于上面的相当于每种元素无限取，而实际上每种元素是有限制的。最多就是其个数。

那么我们其实真的很容易就可以想到容斥。枚举每一种元素超没有，如果第 种元素超了就预先分配 个给他，然后奇偶加减类容斥就完了。一般的排列也有类似的方法，这里不做赘述。

bsgs与exbsgs

BSGS(大步小步) 可以在 的时间内求解出 的最小解，满足 是质数。思路如下：

因此我们枚举 ，将 最后一次出现的位置的 存到 对应的位置（一般用 unordered_map），直接覆盖原有数据就行。

接下来，我们顺序枚举 ，一旦发现在 unordered_map 中存在 ，就直接返回 。如果 枚举完了还没有返回就只能是无解了。

不难注意到 ，无法枚举到 ，因此需要特判这种情况。

在 较小的情况下 越大 越小。正确性比较显然，时间复杂度也必然正确。

哈哈，数论题的拓展最喜欢的就是去除各种互质/是质数一类的限制了！他也跑不掉。思路如下：

于是问题被转化为普通的 BSGS。注意上面 不一定是质数，因此 的逆元要使用 EXGCD 求解。

生成函数

一些前置概念，在后面多个板块会用到。

积性函数：满足 。

那么，知道因式分解时有：

。

常见积性函数：

： 时为 的因子数，。

：莫比乌斯函数。

：欧拉函数。

： 的约数个数。

：。

。（常见写为 ）。

。（常见写为 ）。

普通生成函数

对于数列 ，其 OGF 为 。

看起来不知道有什么用，给个例题：有三种物品，每种物品分别有 个，问从这三种物品里面拿出 个的方案数有多少种？

假设 ：转移到物品 ，已经选了 个。

能不能更方便一些？

对每一个数生成出其生成函数()，即 ，。令 ，则答案为 ，即 的系数。

其实生成函数的系数之间的乘法对应了你手数时每一项选择的过程。

需要注意的是，这些生成函数往往可能会涉及到无穷的累加。请别忘了我们还有展开式，无穷序列加起来可能会变成之前的分式。

典型手算例题有《干饭》和《末日时在干什么》。（不正经.jbg）

其实我们不难看出，绝大多数的情况下， 数组都只会涉及到 两种值，来表示可不可取。拆解的时候多使用换元法，因式分解法，往往会有奇效。

补充一个公式：。

指数生成函数

对于数列 ，其 EGF 为 。

对于大部分带标号的问题，可能会有类似的形式：。一个典型的例子就是多重集的排列。

有 ，即 。

因此这么定义。这里较为常用的公式是关于 的泰勒展开。

有一个公式需要记一下：

。证明显然，展开后就是了。

一个典型的应用就是求可重集的排列数。如题，代码如下：

狄利克雷生成函数

对于无穷数列 ，其 DGF 为 。

如果 满足积性，那么其 DGF 也可以由质数幂处的取值表示为 。

有一些常见的 DGF，可以记一下。

黎曼函数 可用序列定义为 ，另一种形式为 。

莫比乌斯函数的 DGF 定义为 。也就是说，。

欧拉函数的 DGF 定义为 。也就是说 。

狄利克雷卷积

若 ，则令 。

积性，则 积性。

若 ，则称 互逆。

可以做到 求 或 。

对于其余的卷积，其复杂度一般为 ，调和级数。

莫比乌斯反演

本质：。

证明：。

其中的 指 的质因子个数。

，。

则有 ，。显然，函数的逆放到这里一定成立。

主要应用就是拆 。套路就是去枚举 的值，然后对取等条件作卷积。

最常用的场景就是 ，尤其是 的形式。

一种较为常见的形式是求 。这时候我们构造函数 ，满足 。原式转化为 。

典型例题就是这道题。

亚线性筛法

杜教筛

杜教筛是个神奇的东西，对于 ，满足 的函数，也就是积性函数，它可以在 的时间复杂度内求出 。通过合适的预处理可以降到 。

具体的，对于一个积性函数 的话，我们可以知道 。

其中 表示的是迪利克雷卷积。

于是，我们可以使用记忆化与整除分块来做上述操作。时间复杂度证明略。注意当且仅当处理到了 的时候才有 的求解复杂度。递归求解即可。

模板题在这里。

PN筛

min_25筛

https://www.luogu.com.cn/article/m8uwkv2f

第一类斯特林数

第一类斯特林数有通用标记：。他表示的组合意义是将 个人分配到 个非空环上的本质不同的方案数。其中环不作标号区分，人做区分。

那么它怎么求呢？显然我们可以整出来一些递推式。我们怎么从 推到 呢？也就是多了一个人会多产生哪些情况呢？

首先，它可以新开一桌，从 推到 ，系数为 。

其次，他可以加入原有的位置。显然，因为是圆桌， 个人就会有 个本质不同的空隙。因此可以从 推到 ，系数为 。

从而，。边界条件为 。

通过其组合意义，我们可以推知如下式子：

比如有这么一个例题。思路就是将能看到的和被他挡住的视为一个环进行求解。

第二类斯特林数

第二类斯特林数也有通用标记：。他表示的组合意义是将 个人分配到 个非空无序集上的本质不同的方案数。其中环不作标号区分，人做区分。

那么它怎么求呢？显然我们可以整出来一些递推式。我们怎么从 推到 呢？也就是多了一个人会多产生哪些情况呢？

首先，它可以新开一个集合，从 推到 ，系数为 。

其次，他可以加入原有的位置。显然，本质不同的就是 个集合。因此可以从 推到 ，系数为 。

从而，。边界条件为 。

通过其组合意义，我们可以推知如下式子：

这个例题就行，一眼差不多能出思路，而且不太板。

斯特林反演

按照之前的整理，其本体其实长这样：

若，则 。

若，则 。

不过，这次我们着重讲的是 和 之间的转化。

所以，要下降幂干什么呢？下降幂有如下两种美丽的变化：

。这两个看起来就挺有用的。

所以，怎么变呢？

。

。

可以通过组合意义较容易地证明出下面的那个式子。或者数学归纳法也是可以的。如图：

变换完之后可能可以和前面的一些项合并，换位等，得到一个好处理的式子。

这两天没有自己手推出来的比较好的式子，放一个题解做样例吧，对应这道题。

二项式反演

flag。

若 ，则 。

证明：错排问题。

我们让 表示 个人随便站的方案数， 表示恰好 个人站错的方案数，显然满足了第一个式子，而对于第二个式子而言也是适用的。

二项式反演可以实现“至多”/“至少”和恰好之间的转化。

同理也有：若 ，则 。

上述的两个式子是比较常用的两个。从本质思想来讲呢，这两个式子都是类似于容斥的形式推出来的。

也就是说，如果我能够构造出来一对合理的 ，那他一定对应着一种组合意义下的容斥方式。

所以，二项式反演提供了一种更加快速的找容斥关系的方式，而容斥因其逻辑更加底层，反而能解决更多的题。

当然这么说有点绝对。既然是一个反演，那他一般有超出其根源的用途。在解决一些计数问题的过程中，二项式反演公式对简化问题有着重要的作用。只是例题目前不太有体现。

burnside定理

Burnside定理：。其中 是所有置换所构成的集合， 是置换 对应的本质不同的集合的个数。

怎么理解呢？例题：有 种颜色的珠子，你要用他们来构成一个有 个珠子的手环，问有多少种本质不同的手环。这里本质不同定义为旋转或翻转后二者仍不同。

那么，其置换包括旋转 度，沿对角线/对边线翻转，共 种。 是指的置换 对应的本质不同的集合的个数。也就是求经过置换 后仍一样的方案数。

例如：

对角线上的分别属于两组，因此总共有 种本质不同的手环。

总共有三组，因此共有 种本质不同的手环。

因此，最终的答案为 种。分子上的每一项依次对应转 度，两种沿着对边翻，两种沿着对角翻。

往往需要静下心来推一下 ，给一道例题。

polya定理

Polya 定理可以视为是 Burnside定理在较简单的问题上的特例化。其式子如下：

。

肉眼可见的，这里我们认为 。而如果我告诉你 表示的是置换 的循环节数，这里的循环节是指的有向移动形成的环，那么这个公式的意义就更加明了，甚至不证自白了。

另给一道例题。

博弈论

博弈论主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。

在 OI 中，我们也有时会遇到这些题。其中最常遇到的是公平组合游戏。参考这篇博客。

首先，在 OI 当中，我们常研究的是平等博弈，也就是说，可允许的操作只和当前局面的状态而和操作的玩家无关。

公平组合游戏

若一个游戏满足：

  1. 有两名玩家交替行动；
  2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关； 3.不能行动的玩家判负。

则称该游戏为一个公平组合游戏。

这时候有一些比较重要的概念：有向图游戏，必胜态和必败态。

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿着有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

那么不难发现，任何一个公平组合游戏都可以转化为有向图游戏。游戏状态为点，状态转移为边。

必胜态：存在一种策略，可以让剩余的状态变成必败态留给对手的局面。

必败态：不管采取什么策略，这一步行动后对手都处于必胜态的局面。

简化一下，就是三个定理，这也是博弈论的核心：

这里举出若干公平组合游戏的例子。

Nim 游戏：

地上有 堆石子，其中第 堆有 颗石子。每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否有先手必胜策略。

这时候，我们似乎无从下手，那让我们从有向图游戏的角度去下手，考虑图上的必胜态，必败态。

首先，有一个必败态是剩余石子全为 。不难发现他们全部异或起来为 。

随后我们发现了一个不得了的可能正确的结论：当且仅当 时先手必败。

先证一个引理：当 时，必定存在方案，将其中一个数变小之后满足 。

因为异或是二进制下的不进位加法，也就意味着异或值的最高位一定有至少一个数是 。这时候我们取其中任意一个数异或上现在这个值，他的值一定变小了，而且现在异或起来的值显然为 。

首先，充分性很容易证明。当先手拿掉一些石子，使其异或值变化时，我们一定存在一些方案使得其异或值变为 ，也就是我们的引理。

必要性呢？当 的时候我们可以构造使得 。而 是必败态，从而 是必胜态，也就是说必败态只可能 。

证毕。题目。

台阶 Nim 游戏：

有 级台阶，第 级上有 颗石子。每人每次可从任意一堆石子里取出任意多枚石子放到下一级台阶上，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否有先手必胜策略。

首先，我们可以认为偶数级台阶上的是无效的。因为先手将若干颗移动到下一及后，后手可以再将这些石子移动到下一级从而将这堆石子再次移动到偶数级，最终移到 。

于是我们发现，将石子从奇数阶移动到偶数阶就是丢弃，将石子从偶数阶移动到奇数阶如果不能使奇数阶上的石子数异或值为 就是白给。

而我们只通过将石子移下奇数阶就可以做到使奇数阶上的石子数异或值为 。

从而得出结论： 时先手必胜。

证毕。题目。

Moore's Nimk：

两个人玩取石子游戏，共有 堆石子，每个人每次可以从不超过 堆石子里面取任意多个石子（不能不取），不能取的人输。问先手必胜条件。

给出结论了就可以用类似于上面的方法整出来了：将每一个数写成二进制形式，则如果每一位上 的个数都是 的倍数，则先手必败，否则先手必胜。

这个有前面的铺垫，读者自证不难？就不赘述了。

还有两个可能见到的，记一下结论就行了，因为证明有点怪怪的，有点脱离了我们之前所构建的体系，所以不详讲。

Wythoff 博弈：

有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。判定先手是否必胜。

先手必败当且仅当 ，非严格判等，整数部分一样即可。

证明。例题-1，例题-2。

Fibonacci 博弈：

一堆个数为 的石子，有两条规则：

  1. 先手不能在第一次把所有的石子取完，至少取 颗
  2. 之后每次可以取的石子数至少为 ，至多为对手刚取的石子数的倍。

约定取走最后一个石子的人是赢家，求先手必胜态。

先手必败当且仅当石子数为斐波那契数。题目。

SG 函数

这个也是相当的重要的。

首先有一个函数 。

假如说状态 有 个后继状态 ，那么 。

由于一般情况下没有后继状态的可以视为必败态，因此 必败，反之必胜。因为 与必败必胜态极好的对应关系，其正确性不证自明。

最直接的应用就是 Bash 博弈和其拓展：集合型 Nim 游戏。

Bash 博弈：

总共有 个石子，每次每人可以取 个石子，问先手必胜状态。

先手必败当且仅当 。非常裸的 SG 函数，。递推可证。题目。

集合型 Nim 游戏：

给定 个整数组成的集合 , 给定 堆石子的数量 , 两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须是集合 中的整数，最后无法操作的人失败。判定先手是否必胜。

直接暴力推 SG 函数值就行了。题目。

移棋子游戏：

给定一个有 个节点的有向无环图，图中某个节点上有棋子，两名玩家交替移动棋子。对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。

这样的话仍旧是非常裸的 SG，那我问你，如果图上有多个棋子呢？

答案很眼熟：当且仅当每个棋子的 SG 值异或起来为 时先手必败证明：

不难发现这个问题和丢石子的那个问题是很像的。当你在某个非零状态下时你可以丢掉任意颗。虽然即使你一颗都不剩，你也可能可以做到增加，毕竟求的是 ，但是这也意味着对手恒存在一些方法能给你变回来。当你不存在增加的变换的时候你的旅途也就到此为止了，只能老老实实地减。

而又因为你在某个非零状态下时你可以丢掉任意颗，所以你总能维护异或值为 。

证毕。题目。

相关的有许多变种，比如 Anti-SG，Multi-SG，Every-SG，可以自行参阅开头的博客。

随便给几道例题：1，2，3。

二次剩余

求解同余方程 。你可以假定 有解且 为奇素数。

若方程 有整数解，则称 为模 的二次剩余，否则称 为模 的二次非剩余。

先给出结论：寻找一个整数 满足 为模 的非二次剩余，并定义 。答案就是 。

额，后面会证明出来 没有“虚部”。

二次剩余判定定理

是 为模 的二次剩余的充要条件。

必要性显然，充分性：

令 ，其中 为模 意义下的原根。

将 带入，得 ，所以 ，所以 ，即 是偶数。

所以， 为原方程的解，即 为模 的二次剩余。证毕。

同时我们也可以发现，因为 ，所以 ，也就是说， 是 为模 的二次非剩余的充要条件。

他至多有 个不同的解

假定 是其中任意两个解，则 ，则 。因此 或者 。因此最多只有两个不同的解。

以上两个定理保证了可解性。

接下来，我们推 ，看看是什么东西。

又因为存在性定理，显然当存在解时会分别得出两个根，或者干脆就是 。因此 没有“虚部”。

你问我怎么找合适的 的话，其实不难发现二次剩余和二次非剩余正好一半一半，随机化的话期望 次就能找到。相信自己的运气不会差到抽中 。

线性基

线性基，其概念可以视为向量的基底。

也就是说，假设给定元素集 ，你可以构造出来另一个集合 ，使得 中所有元素都可以用 中的元素表示，而 中任意一个元素都没法只使用 的其他元素表示出来。

不管怎么说，由于任何意义下的向量的美妙的性质，我们一定要保证 中的每一个元素的第一个非零位置不重。

而这个东西在信息中，应该能感觉到是生来就有用的。毕竟他给出了一大坨信息的一种高效压缩方式。

事实上的确如此。在信息中，我们更多研究的是异或线性基。也就是说，我们只用 中元素进行异或操作。

这个博客就挺好。另外，由于贪心能支持的面超过了高斯消元，且可以在 的复杂度内转化，所以不整理高斯消元。

异或线性基

贪心怎么贪呢？首先从高位向低位扫，当这个数这一位是一时，如果线性基中没有元素最高位是当前位，那就把它放到线性基中，否则把他异或上线性基中的那个元素，继续进行。

接下来，我们可以应用一下，比如我们现在要求出来一堆数的最大异或值。

显然，我们从大到小去枚举，如果当前这一位为 并且这一位有线性基，那就异或一下，否则不动。代码如下：

但是这样还没完。如果很不巧他让你求 小异或值，那你线性基不就炸了吗？

不好意思，没炸。仔细想一下，会导致大量策略出问题的地方就在于判断这一位为 并且这一位有线性基。如果这一位有线性基就可以毫无顾虑地异或是不是就很简单了？

欸？如果我们强制保证是最高位的那些位仅在那一位的线性基上是 不就做完了？

所以我们只需要对每个最高位的线性基进行检查，具体的如果比它更小的线性基在这一位有值就异或上他。从小到大进行检查即可。

或者，你用小线性基去消大线性基也是一个道理。当然这还没有结束，我们还需要求 小异或值。

解除了刚才的制约，我们真的不难想到，当你选择了更大的线性基的时候，小的线性基也无力回天。

大的严格压制小的，且不影响小的，那就和线段树上二分等等的没区别了。更加明显的，每一次选与不选恰是 的二进制位！

唯一需要注意的就是有没有 了。代码如下：

前缀线性基

这就很有生活了。他可以求解出一个数组在区间内的最大异或值！

怎么做到的呢？一句话：我只要最新版本。在下标 时，先将 位置的线性基拷贝过来，然后尝试加上 位置的数。如果遇到空位就直接填进去。

如果这一位是 且此位有线性基，那就比较二者的最后更新时间（初始状态下当前持有值的最后更新时间为 ），如果持有值更新，就顶替原有值，并将手上拿的改为原有值。

做完了操作之后再异或一下手上的值（和线性基值），直到手上的值为 或者填上坑了。

代码如下：

求 的时候，第 位的线性基有效当且仅当这一位的最后更新时间在 及以后。

数论线性基

这个名称可能不严谨，但是确实能让我们知道他和异或线性基的区别。数论线性基可以理解为一堆向量的大小最小的基底。

这甚至更简单。就是拿着贪心的思路暴力模拟就完事了。

字符串

字符串哈希

为什么这个东西放在了最前面呢？道理很简单。这个东西很简单，但是能替代部分需要用一些略显复杂的算法才能维护的东西。

假定我们现在有一个字符串 ，下标从 到 。那么 位置对应的哈希值 为 。

其中， 为一个选定的至少比 的字符集大的质数（常用 ）， 是对 字符集到数字的唯一对应， 是一个指定的模数。有时用 unsigned long long 的自然溢出，即 ，但是容易被卡，所以 也常用一些大质数（常用 ）。

也有递推的形式，更加常见：。

那么具体怎么用呢？哈希最常用的用处就是判断两个量相不相等。用哈希来比较两个完整串显然大材小用，一般他会用来比较多个字串是否相等。

对于 到 的字串，其哈希值为 。

显然，对于任意的字符串，只要你选取的 映射方式和 数一致，那么对于任意的相同子串的哈希值也是一样的。下证：

看回 的直接计算形式，并带回哈希值计算方法，发现其值为 。我们令这个子串为 ，不难发现，对 整个串做哈希，其值为 。又因为 ，所以 。

也就是说，用一个字符串 去截取子串所得到的哈希值，等于这个子串本身的哈希值。那么任意一个串中去截取同样的一段得到的哈希值也必然是一样的。

于是，恭喜你，得到了一种快速比较两个子串是否一样的方法。其作用不用我说也是相当大的。

kmp

主要是最长 。一般记一个串在 位置的最长 为 。

最长 指以位置 结束且是字符串前缀的子串的最大长度。 表示以位置 开始且是字符串前缀的子串的最大长度。特别约定 。

那 KMP 怎么玩 呢？

暴力求解可以被形如 的串卡到 ，我们需要一些性质来优化。

假设有一个串，我们来求他的 ，并且已经求出了前 位的值。

在考虑 位置的时候，我们不难发现，。这一点可以使用 的性质使用反证法非常方便的证明出来，不作赘述。

但是只是用这一点的话并不能做出什么特别有效的优化，毕竟往回跳的时候会需要 的验证，整体是 的。

再接着思考一下，当 的时候，。当 时，我们则希望找出一个仍满足 的性质，且长度最长的一个前缀兼后缀字串。这至少可以告诉我们，这两个字符串除最后一个字符以外的字符一定一模一样。

仔细想一下，因为现在我们有每一个前缀字串的最长公共前后缀，对于一个最长公共前后缀的最长公共前后缀，他也一定仍然是原前缀子串的公共前后缀。也就是说，在长度尽可能长的情况下， 会是我们第二个考虑的可能的字符串。如果仍然不对，我们就一直考虑 ，直到上述值为 （即不存在符合要求的公共前后缀）或找到一个符合要求的值，使得 。

这样，因为每一次 都至多增大 ，而且后退的次数一定不大于前进次数，因此复杂度为 。

其实说起来复杂做起来简单。核心代码大概就是 行的样子。那这个 有什么用呢？

很简单，字符串匹配。对于一个主串 和一个模式串 ，它可以用 的时间求解出来 在 中出现了多少次。

我们回忆一下暴力匹配的过程：从头匹配，遇到不符合就匹配下一个位置，直到匹配完匹配串。

再思考一下最长 的性质，不难发现，如果这一个位置匹配不上，那么他的最长 位置是最长的仍与前面的字符匹配的前缀子串。也就是说，我们没必要从头开始匹配，而是变相的从这个位置继续，改变已匹配的位置之后接着匹配。

这样做显然不会漏解，要是漏了，就与最长 的性质相违背。

对于【模板】KMP 而言，他就是问你 的 函数值和 在 出现的位置。可解。

exkmp

主要是 函数。一般记一个串在 位置的 为 。那 EXKMP 和 是什么呢？

这里有你没写完的东西，杂鱼...

后缀自动机

SAM 虽然叫做后缀自动机，但实际上他对于所有子串的优秀的压缩效果及其用途才是我们更为关心的。直观上，字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。实质上，字符串 的 SAM 是一个接受 的所有后缀的最小 DFA。

首先，SAM 本身包括这么些东西：

  1. 点（状态），其实就是为了便于边的维护。
  2. 边（转移），边带权，带的是字符集中的某种字符。
  3. 终止状态，如果我们从初始状态 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是原串的一个后缀。原串的每个后缀均可用一条从 到某个终止状态的路径构成。

仅仅考虑这些的话，SAM 就是一个 DAG。

SAM 最重要的性质是，它包含关于原串的所有子串的信息。任意从初始状态 开始的路径，如果我们将转移路径上的权写下来，都会形成原串的一个子串。反之每个原串的子串对应从 开始的某条路径。

到达某个状态的路径可能不止一条，因此我们说一个状态对应一些字符串的集合，这个集合的每个元素对应这些路径。

看起来好像确实非常有用，但是问题在于我们怎么用一个高效的方式给他构造出来呢？实际上，我们可以做到线性时空复杂度。我们需要两个非常重要的东西：结束位置(endpos)和后缀链接(link)。

结束位置(endpos)

考虑字符串 的任意非空子串 ，我们记 为在字符串 中 的所有结束位置（假设对字符串中字符的编号从零开始）。例如，对于字符串 ，我们有 。

两个子串 与 的 集合可能相等：。这样所有字符串 的非空子串都可以根据它们的 集合被分为若干等价类。

显然，SAM 中的每个状态对应一个或多个 相同的子串。换句话说，SAM 中的状态数等于所有子串的等价类的个数，再加上初始状态。SAM 的状态个数等价于 相同的一个或多个子串所组成的集合的个数 。

endpos 有若干定理性质， 中写了三条，但其中 条均可由第 条得到：

若 ，则：

正确性显然。

后缀链接(link)

考虑 SAM 中某个不是 的状态 。我们已经知道状态 对应于具有相同 的等价类。我们如果定义 为这些字符串中最长的一个，则所有其它的字符串都是 的后缀。

我们还知道字符串 的前几个后缀（按长度降序考虑）全部包含于这个等价类，且所有其它后缀（至少有一个——空后缀）在其它的等价类中。我们记 为最长的这样的后缀，然后将 的后缀链接连到 上。

换句话说，一个后缀链接 连接到对应于 的最长后缀的另一个 等价类的状态。

与之相关的也有两个性质定理：

所有后缀链接构成一棵根节点为 的树。

通过 集合构造的树（每个子节点的 都包含在父节点的 中）与通过后缀链接 构造的树相同。

这两个性质放一起构成了 SAM 构造中最重要的理论依据。现在我们终于可以讲构造过程了。这个算法是在线算法，我们可以逐个加入字符串中的每个字符，并且在每一步中对应地维护 SAM。任务转化为实现给当前字符串添加一个字符 的过程。一开始 SAM 只包含一个状态 ，编号为 （其它状态的编号为 ）。为了方便，对于状态 我们指定 （ 表示虚拟状态）。算法流程如下：

  1. 令 为添加字符 之前，整个字符串对应的状态（一开始我们设 ，算法的最后一步更新 ）。
  2. 创建一个新的状态 ，并将 赋值为 ，在这时 的值还未知。
  3. 现在我们按以下流程进行（从状态 开始）。如果还没有到字符 的转移，我们就添加一个到状态 的转移，遍历后缀链接。如果在某个点已经存在到字符 的转移，我们就停下来，并将这个状态标记为 。
  4. 如果没有找到这样的状态 ，我们就到达了虚拟状态 ，我们将 赋值为 并退出。
  5. 假设现在我们找到了一个状态 ，其可以通过字符 转移。我们将转移到的状态标记为 。
  6. 现在我们分类讨论两种状态，要么 ，要么不是。
  7. 如果 ，我们只要将 赋值为 q 并退出。
  8. 否则就会有些复杂。需要复制状态 ：我们创建一个新的状态 ，复制 的除了 的值以外的所有信息（后缀链接和转移）。我们将 赋值为 。
  9. 复制之后，我们将后缀链接从 指向 ，也从 指向 。
  10. 最终我们需要使用后缀链接从状态 往回走，只要存在一条通过 到状态 的转移，就将该转移重定向到状态 。
  11. 以上三种情况，在完成这个过程之后，我们将 的值更新为状态 。

算法本体讲解完毕，模板题代码：

看看这个：yutong.site/sam/。

那他的应用呢？挺多的，列例题讲解吧。

T0,【模板】后缀自动机（SAM）,省选，板子题。

T1-1,SUBLEX,省选&&T1-2,[TJOI2015] 弦论,省选，SAM 求字典序第 大子串。

HINT：字典序第 大的子串对应于 SAM 中字典序第 大的路径，因此在计算每个状态的路径数后，我们可以很容易地从 SAM 的根开始找到第 大的路径。

T2,【模板】最小表示法,提高省选，SAM 求最小表示法。

HINT：容易发现字符串 包含字符串 的所有循环移位作为子串。所以问题简化为在 对应的后缀自动机上寻找最小的长度为 的路径。

Query：你还记得他的更简便的求法吗？

T3-1,LCS,省选&&T3-2,LONGCS,省选&&T3-3,LCS2,省选，SAM 求两个/多个字符串的最长公共子串。

HINT1：求两个的话，我们可以构造出一个字符串的 SAM，我们现在处理另一个字符串，对于每一个前缀，都在 SAM 中寻找这个前缀的最长后缀，求最大值即可。转移的时候，类似于 KMP 的跳 ，ACAM 的跳失配指针，我们跳后缀链接并更新长度即可。

HINT2：求多个的话，我们将所有的子串连接成一个较长的字符串 ，以特殊字符 分开每个字符串（一个字符对应一个字符串）：。然后对字符串 T 构造后缀自动机。答案就是最深的且它的子树中具有所有分节符的非叶子节点。

T4,[SDOI2016] 生成魔咒,省选，动态求本质不同子串的个数。

HINT：每次新出现的本质不同的子串个数就等于 。

还有很多啊，比如出现次数，第一次出现的位置，所有出现的位置等，但是大多可以用 ACAM 吃掉。

依据这个帖子，SA 胜过 SAM 的地方在于 SAM 不能（或者很难） 比较两个后缀的字典序（by 366338），而 SAM 中的 却可以用来干很多恶心人的事。不过，二者似乎可以在 的时间内互相转化，因此不太存在只能用其一解的题。

Tip：有的文章会说在牺牲一点点效率的情况下可以做到严格线性的空间复杂度，带 或常数的时间复杂度，但是实际上，map<int,int> 在 gcc 下初始状态下会占 ，unordered_map<int,int> 更是会占到 。前者相当于 个 int，后者相当于 个 int。因此，实际应用中（多为小写字母 大小字符集），可以酌情选择前者，一定不要选择后者。

后缀数组

部分进阶知识可以参见这篇集训队论文。

SA，全称 ，译为后缀数组。 在所有后缀中的字典序升序排名的第 个后缀的开始位置，表示的是 表示的是后缀 在所有后缀中的字典序升序排名。 表示 。

怎么求 呢？首先有一种暴力的 的做法。我们将所有的后缀拿过来排序。这不是 的吗？但事实上，比较两个字符串就是在比较它们第一处不一样的位置的大小。因此我们可以用 Hash+BinarySearch 优化到 。

但是这样做时间复杂度仍然有些高，能不能优化到 呢？可以，不过我们换一种方式。

假如说我们已经排出了这些后缀在考虑前 个字符时的大小，那么怎么拓展到 个字符呢？显然我们只需要对有序二元组 排序就行了。正确性显然。

但是这样不还是 的吗？不是。不难注意到 ，也就是说我们可以不基于比较进行排序。我们采用计数排序。

欸？二维的怎么计数排序？很简单啊，先把第二维升序排了再把第一维顺序排了。

那你的 数组怎么处理？最后处理吗？显然不是，计数排序的时候我们就需要 数组。但是一定要注意 只在两维都排完之后才会更新。毕竟两次排序本质上是一次二维排序。你中间就把排名改了能对就怪了。

这样就优化到 了。还能更优吗？可以。你可以使用 SA-IS 算法做到 ，他要更优于 DC3。为什么？因为提高了缓存命中率（喜）。

这不重要，来看 数组吧。首先很显然， 数组仍然可以用 Hash+BinarySearch 做到 ，但是能不能更优呢？

可以的。很难(?)注意到一个性质：。总之，有了这个性质，我们就可以暴力模拟这个性质获得 的简短的算法。为什么是 呢？因为最多 次减一，对应最多 次加一。

比模板题更模板的模板题代码如下：

小技巧

区间加转差分

这种技巧非常常见而且十分灵活。常见于用来优化数据结构，比如树状数组处理区间加区间求和。这里另提一道好题：Power Tree。

看起来和这个技巧真的毫无关系，但是我们发现如果我们用 dfs 序把这颗树给拍扁了，那控制一个顶点就相当于可以对一个连续的区间进行区间加。这时候，我们区间加转差分，相当于每一个点可以将一个位置的贡献总和不变的挪动到另一个位置。

我们最后的目标是所有点的值是 ，也就是在前 个位置的差分数组总是为 ，因此我们可以使用最小生成树来将选择可用边，使得其总能转移到 这一限制条件转化为最小生成树！

于是我们将树上的问题先通过 dfs 序转化为了序列加，再将序列加通过差分转变为点值移动，最后抽象出最小生成树的图论模型解决，十分巧妙。